package com.cjl.demo.data.treenode;

import java.util.Arrays;

/**
 * 二叉搜索树
 * 给一个无序且无数值重复的数组，输出根据这个数组元素顺序构成的二叉搜索树的层级（设根节点为第1层）。
 * 例如：
 * int[] arr= {2,3,8,9,4,5,1,7}
 * 输出6
 */
public class BinarySearchTreeTest1 {
    public static void main(String[] args) {
        int[] arr= {2,3,4,5,7,8,9};
        TreeNode root = sortedArrayToBST(arr);
        System.out.println("args = " + root.val);
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);//递归建树
    }

    public  static TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {//递归出口
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点，这里选择的策略不同，建立的树就不同
        int mid = (left + right) / 2;
        //二叉搜索树的中序遍历是升序的
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, left, mid - 1);
        root.right = helper(nums, mid + 1, right);
        return root;
    }

}

/**
 * 树节点
 */
class TreeNode {
    TreeNode left;
    TreeNode right;
    int val;
    int level;

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

}